//  GraphList.cpp
//  深度优先遍历
//
//  Created by 橘子和香蕉 on 2018/11/25.
//  Copyright © 2018 橘子和香蕉. All rights reserved.
//


/*
 遇到的问题：
 1:首先是添加边；用户输入的两个结点，先要判断哪个结点是新添加的，是俩都是，还是一个是，，然后设置位置。添加结点先是将数据放在数组，然后要将它添加到相应的链表中去，那就要申请新结点，我就是在初始化结点的时候没有将结点中指针设置为NULL，才导致了我之后的错误，想想就觉得自己蠢。
 */

#include <iostream>
using namespace std;
#define dataType char
#define MAXSIZE 100 
typedef struct  node{
    int position;
    node *next;
}node;
typedef struct Box{
    dataType data;
    node *out;
    bool isAccess;
}Box;
class Graph{
private:
    Box base[MAXSIZE];
    int vertexNum;
    int edgeNum;
    int  locate(dataType data);
    
    void deleteEdgePrivate(int  startPosition,int endPositon);
    void def(int position);
    bool isNotHaveNevNode(dataType data);
    void moveNode(dataType data);
    
public:
    ~Graph();
    void init(int vertexNum,int edgeNum);
    void create();
    void printNode(dataType data);
    void printGraph();
    void addEdge(dataType start,dataType end);
    void deleteEdge(dataType start,dataType end);
    void depthErgodic(dataType data);
    
};
Graph::~Graph(){
    for (int i = 0; i<vertexNum; i++) {
        node  *p= base[i].out;
        node *h = p;
        while ( p != NULL) {
            
            h = p->next;
            if(h == NULL) return;
            delete p;
            p = h->next;
        }
    }
    //    delete []base;
}
void Graph::init(int vertexNum, int edgeNum){
    this->vertexNum = vertexNum;
    this->edgeNum = edgeNum;
}
int  Graph::locate(dataType data){
    for (int i = 0; i<vertexNum; i++) {
        if(base[i].data == data){
            return i;
        }
    }
    return -1;
}
void Graph::create(){
    cout<<"create Graph begin\n";
    for (int i = 0; i<vertexNum; i++) {
        cout<<"input node data\n";
        cin>>base[i].data;
        base[i].out = NULL;
        base[i].isAccess = false;
    }
    node *startNode,*endNode;
    int startPosition;
    int endPosition;
    dataType start;
    dataType end;
    for (int i = 0; i<edgeNum; i++) {
        cout<<"input edge start and end\n";
        cin>>start>>end;
        startPosition = locate(start);
        endPosition = locate(end);
        //创建链表。先是创建start指向end;
        //在创建end指向start；
        endNode = new node;
        endNode->position = endPosition;
        endNode->next =  base[startPosition].out;
        base[startPosition].out = endNode;
        
        startNode = new node;
        startNode->position = startPosition;
        startNode->next = base[endPosition].out;
        base[endPosition].out = startNode;
    }
    
    
}
void Graph::printNode(dataType data){
    int position = locate(data);
    if(position == -1){
        cout<<"data is not exist\n";
        return;
    }
    else{
        node *h = base[position].out;
        cout<<"the data of"<<data<<":\t";
        while (h!=NULL) {
            cout<<base[h->position].data<<"\t";
            h=h->next;
        }
    }
    cout<<"\n";
}
void Graph::printGraph(){
    for (int i = 0; i<vertexNum; i++) {
        printNode(base[i].data);
    }
}
void Graph::addEdge(dataType start, dataType end){
    
    int startPosition = locate(start);
    int endPosition = locate(end);
    if(startPosition == -1){
        base[vertexNum].data = start;
        base[vertexNum].out = NULL;
        startPosition = vertexNum;
        init(vertexNum +1 , edgeNum+1);
    }
    if(endPosition == -1){
        base[vertexNum].data = end;
        base[vertexNum].out = NULL;
        endPosition = vertexNum;
        init(vertexNum +1 , edgeNum+1);
    }
    if(startPosition == -1 && endPosition == -1){
        
        base[vertexNum].data = start;
        startPosition = vertexNum;
        init(vertexNum +1 , edgeNum+1);
        
        base[vertexNum].data = end;
        endPosition = vertexNum;
        init(vertexNum +1 , edgeNum+1);
    }
    node* endNode = new node;
    endNode->position = endPosition;
    endNode->next = base[startPosition].out;
    base[startPosition].out = endNode;
    
    node* startNode = new node;
    startNode->position = startPosition;
    startNode->next = base[endPosition].out;
    base[endPosition].out = startNode;
    
    
}


void Graph::deleteEdge(dataType start, dataType end){
    
    /*
     a：删除的时候要判断俩结点的位置，然后一个一个的删除，先是删除start 到end这条表
        然后接着删除end到start这条边；
        其实删除的操作都是一样的，然后我就将删除的操作独立了出来，写了一个函数，放到private中去，
        删除start 到end和删除end到start只不过就是在函数调用的时候颠倒就好了，但是这只限于无向图。
     */
    int startPosition= locate(start);
    int endPositon = locate(end);
    if(startPosition ==-1 || endPositon == -1){
        cout<<"node is not exist\n";
        return;
    }
    deleteEdgePrivate( startPosition,endPositon);
    deleteEdgePrivate(endPositon, startPosition);
    if( isNotHaveNevNode(start) == true){
        moveNode(start);
    }
    if(isNotHaveNevNode(end) == true){
        moveNode(end);
    }
}


void Graph::deleteEdgePrivate(int  startPosition,int endPositon){
    int n = 0;
    node * p = base[startPosition].out;
    node *h = base[startPosition].out;
    
    
    while (p != NULL) {
        
        if(n ==0 && p->position == endPositon ) {
            base[startPosition].out = p->next;
            delete p;
            return;
        }
        n++;
        if(n != 0 && p->position == endPositon){
            h->next = p->next;
            cout<<"  "<<base[p->position].data<<endl;
            delete p;
            return ;
        }
        h = p;
        p = p->next;
    }
}

void Graph::depthErgodic(dataType data){
    int position = locate(data);
    position == -1?cout<<"the data is not exist\n":cout<<"";
    def(position);
    
}
void Graph::def(int position){
    node *p;
    cout<<base[position].data<<endl;
    base[position].isAccess = true;
    p = base[position].out;
    
    while (p != NULL) {
        if(base[p->position].isAccess == false){
            def(p->position);
        }
        p = p->next;
    }
}
/*p
 判断还有没有邻结点
 */
bool Graph::isNotHaveNevNode(dataType data){
    int position = locate(data);
    return  base[position].out == NULL?true:false;
}
/*
 移动数据
 */
void Graph::moveNode(dataType data){
    int position = locate(data);
    for (int i = position; i<vertexNum ; i++) {
        base[i].data = base[i+1].data;
        base[i].out = base[i+1].out;
        base[i].isAccess = base[i+1].isAccess;
    }
    this->vertexNum -= 1;
}
int main(){
    Graph a;
    a.init(4, 4);
    a.create();
//    a.printNode('b');
//    a.printGraph();
    a.addEdge('d', 'e');
    a.printNode('d');
    a.printNode('e');
    a.deleteEdge('d', 'e');
    a.printNode('e');
    return 1;
}

